import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/19 21:12
 * @description Floyd算法
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] edges = {{0, 1, 3}, {1, 2, 1}, {1, 3, 4}, {2, 3, 1}};
        solution.findTheCity(4, edges, 4);
    }
    public int findTheCity(int n, int[][] edges, int distanceThreshold) {
        int INF = Integer.MAX_VALUE / 2;
        int[][] graph = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(graph[i], INF);
            graph[i][i] = 0;
        }
        for(int[] e: edges) {
            graph[e[0]][e[1]] = e[2];
            graph[e[1]][e[0]] = e[2];
        }
        for(int k = 0; k < n; k++) {
            for(int i = 0; i < n; i++) {
                for(int j = 0; j < n; j++) {
                    graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j]);
                }
            }
        }
        int min = Integer.MAX_VALUE;
        int index = 0;
        for(int i = n-1; i >= 0; i--) {
            int cnt = 0;
            for(int j = 0; j < n; j++) {
                if(i != j && graph[i][j] <= distanceThreshold) {
                    cnt++;
                }
            }
            if (cnt < min) {
                min = cnt;
                index = i;
            }
        }
        return index;
    }
}
